/**
 * 创建二叉树
 * @param {number} key 要插入的数值
 * @method insert 插入二叉树节点
 */
function BinaryTree() {
  //节点对象
  let Node = function(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };

  //根节点
  let root = null;

  //插入节点的方法
  let insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
      //如果新节点小于老节点，则插入左节点
      if (node.left === null) {
        //如果老节点的左节点为null,则添加为老节点的左节点
        node.left = newNode;
      } else {
        //如果老节点的左节点不为null，则再与老节点的左节点进行比较并再次做插入
        insertNode(node.left, newNode);
      }
    } else {
      //如果新节点大于老节点，则插入右节点
      if (node.right === null) {
        //如果老节点的右节点为null，则添加为老节点的右节点
        node.right = newNode;
      } else {
        //如果老节点的右节点不为null，则再与老节点的右节点进行比较并再次做插入
        insertNode(node.right, newNode);
      }
    }
  };

  //中序遍历
  let inOrderTraverseNode = function(node, callback) {
    if (node !== null) {
      //如果当前节点不等于空，先左后右的遍历

      //先递归此节点的左节点
      inOrderTraverseNode(node.left, callback);
      //此节点的左节点遍历完成后，输出此节点
      callback(node.key);
      //遍历此节点的右节点
      inOrderTraverseNode(node.right, callback);
    }
  };

  //前序遍历
  let preOrderTraverseNode = function(node, callback) {
    if (node !== null) {
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  };

  //后序遍历
  let afterOrderTraverseNode = function(node, callback) {
    if (node !== null) {
      afterOrderTraverseNode(node.left, callback);
      afterOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  };

  //查找最小值
  let minNode = function(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node;
    }
    return null;
  };

  //查找最大值
  let maxNode = function(node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  };

  //关键字查找
  let searchNode = function(node, key) {
    if (node === null) {
      return null;
    }
    if (key < node.key) {
      //搜索节点如果小于此节点，则递归左子树
      return searchNode(node.left, key);
    } else if (key > node.key) {
      //搜索节点如果小于此节点，则递归右子树
      return searchNode(node.right, key);
    } else {
      //如果等于此节点，则返回节点
      return node;
    }
  };

  //删除节点
  let removeNode = function(node, key) {
    if (node == null) {
      return null;
    }
    if (key < node.key) {
      node.left = removeNode(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = removeNode(node.right, key);
      return node;
    } else {
      /**
       * 如果不包含子树则直接清除
       */
      if (node.left === null && node.right == null) {
        node = null;
        return node;
      }
      /**
       * 只包含一个子树的时候则用子树覆盖当前节点
       */
      if (node.left === null) {
        //如果当前左子树等于null，则用右子树覆盖当前节点
        node = node.right;
        return node;
      } else if (node.right === null) {
        //同理则用左子树覆盖当前节点
        node = node.left;
        return node;
      }
      /**
       * 如果包含左右子树
       * 1、找到右子树里的左叶子树（最小值节点）
       * 2、把左叶子树的key赋值给当前key
       * 3、并删除右子树里的最小值的节点
       */
      let aux = minNode(node.right); //找到右节的最小值
      node.key = aux.key; //赋值给当前key
      node.right = removeNode(node.right, aux.key); //删除右子树里的最小值的节点
      return node;
    }
  };
  //函数接口:插入节点
  this.insert = function(key) {
    let newNode = new Node(key);
    if (root === null) {
      //如果当前根节点为空，则插入根节点
      root = newNode;
    } else {
      //如果根节点不为空，则插入新的节点
      insertNode(root, newNode);
    }
  };

  // 函数接口:中序遍历
  this.inOrderTraverse = function(callback) {
    inOrderTraverseNode(root, callback);
  };

  // 函数接口：前序遍历
  this.preOrderTraverse = function(callback) {
    preOrderTraverseNode(root, callback);
  };

  // 函数接口：后序遍历
  this.afterOrderTraverse = function(callback) {
    afterOrderTraverseNode(root, callback);
  };

  //函数接口：最小值
  this.min = function() {
    return minNode(root);
  };

  //函数接口：最大值
  this.max = function() {
    return maxNode(root);
  };

  //函数接口：查找节点
  this.search = function(key) {
    let bool = searchNode(root, key);
    return bool;
  };

  //函数接口：删除节点
  this.remove = function(key) {
    return removeNode(root, key);
  };
}
